package UnitTest;

import java.util.LinkedList;
import java.util.NoSuchElementException;

/**
 * @Auther: dingtian
 * @Date: 2020 19 49
 * @Description:
 */
public class BinTreeDemo {

    public static void main(String[] args) {
        BinTree tree = init();
        StringBuilder preOrderStr = new StringBuilder();
        preOrder(tree, preOrderStr);
        StringBuilder inOrderStr = new StringBuilder();
        inOrder(tree, inOrderStr);
        StringBuilder postOrderStr = new StringBuilder();
        postOrder(tree, postOrderStr);
        System.out.println(preOrderStr.toString());
        System.out.println(inOrderStr.toString());
        System.out.println(postOrderStr.toString());
        System.out.println(levelOrder(tree));
    }

    /**
     * 先序遍历二叉树
     */
    public static void preOrder(BinTree tree,StringBuilder result) {
        result.append(tree.value);
        if (tree.leftNode != null) {
            preOrder(tree.leftNode, result);
        }
        if (tree.rightNode!=null){
            preOrder(tree.rightNode,result);
        }
    }

    /**
     * 中序遍历二叉树
     */
    public static void inOrder(BinTree tree,StringBuilder result){
        if (tree.leftNode != null) {
            inOrder(tree.leftNode, result);
        }
        result.append(tree.value);
        if (tree.rightNode !=null) {
            inOrder(tree.rightNode, result);
        }
    }

    /**
     * 后序遍历二叉树
     */
    public static void postOrder(BinTree tree,StringBuilder result){
        if (tree.leftNode != null) {
            postOrder(tree.leftNode,result);
        }
        if (tree.rightNode !=null) {
            postOrder(tree.rightNode,result);
        }
        result.append(tree.value);
    }

    /**
     * 层次遍历二叉树
     */
    public static String levelOrder(BinTree tree){
        Queue queue = new Queue();
        queue.enqueue(tree);
        StringBuilder result = new StringBuilder();
        doLevelOrder(result,queue);
        return result.toString();
    }

    public static void doLevelOrder(StringBuilder result,Queue queue){
        if (queue.size()==0){
            return;
        }
        BinTree head = queue.getHead();
        if (head.leftNode!=null) {
            queue.enqueue(head.leftNode);
        }
        if (head.rightNode!=null) {
            queue.enqueue(head.rightNode);
        }
        result.append(head.value);
        queue.dequeue();
        doLevelOrder(result,queue);
    }

    public static BinTree init() {
        BinTree b = new BinTree("b");
        BinTree e = new BinTree("e");
        BinTree g = new BinTree("g");
        BinTree j = new BinTree("j");
        BinTree m = new BinTree("m");
        BinTree o = new BinTree("o");
        BinTree a = new BinTree(null, b, "a");
        BinTree c = new BinTree(a, null, "c");
        BinTree f = new BinTree(e, g, "f");
        BinTree h = new BinTree(f, null, "h");
        BinTree d = new BinTree(c, h, "d");
        BinTree k = new BinTree(j, null, "k");
        BinTree p = new BinTree(o, null, "p");
        BinTree n = new BinTree(m, p, "n");
        BinTree l = new BinTree(k, n, "l");
        return new BinTree(d, l, "i");
    }

}

class BinTree {

    BinTree leftNode;
    BinTree rightNode;
    String value;

    BinTree(String value) {
        this.value = value;
    }


    BinTree(BinTree leftNode,BinTree rightNode,String value){
        this.leftNode = leftNode;
        this.rightNode = rightNode;
        this.value = value;
    }
}

class Queue {
    private LinkedList<BinTree> list = new LinkedList<>();

    public void enqueue(BinTree item)
    {
        list.addLast(item);
    }

    public BinTree dequeue() throws NoSuchElementException
    {
        return list.removeFirst();
    }

    public long size(){
        return list.size();
    }

    public BinTree getHead(){
        return list.getFirst();
    }

    public BinTree getEnd(){
        return list.getLast();
    }
}